package exadel.automatic;
import java.io.IOException;
import java.util.Scanner;
/**
 * Hello world!
 *
 */
public class App 
{
	Scanner con = new Scanner(System.in) ;
	private int cash;
	private int [][]rating = null;				// номинал монеты - вес монеты
	private int [][]unit = null;				// результат выдачи
	private int count;							// count - количество имеющихся монет
	final private int COL = 2;
	final private int EXIT = -1;
	
	public App() {
		this(0);	
	}
	public App(int cash) {
		
		setCash(cash);
		if(cash != 0) {
		try {
			
			System.out.print("number of coins: ");
			count = con.nextInt();					
			rating = new int[count][COL];
			unit = new int [count][COL];
		}
		catch(NegativeArraySizeException ex) {
			System.out.println("the data with error. will use the default value (count = 5). ");
			count = 5;
			rating = new int[count][COL];
			unit = new int [count][COL];
		}
		setRating();
		setUnit();
		}
		else {
			System.out.println("calculation is impossible ...");
		}
	}
	private void setRating() {
		System.out.println("value of coins:");
		for(int i = 0; i < rating.length; i++)
			rating[i][0] = con.nextInt();
		sortRating();
	}
	private void setUnit() {
		for(int i = 0; i<rating.length; i++) 	// добавление номинала в результат
			unit[i][0] = rating[i][0];
	}
	public void setCash(int cash) {
		if(cash > 0)
			this.cash = cash;
		else
			this.cash = 0;
	}
	//Sorting coins
	private void sortRating() {
		for(int i = 0; i<rating.length; i++) {
			for(int j = rating.length - 1; j > i ; j--) {
				if(rating[j-1][0] < rating[j][0]) {
					int temp = rating[j-1][0];
					rating[j-1][0] = rating[j][0];
					rating[j][0] = temp;
				}
			}
		}
	}
	//Сalculation of weights for coins
	private int weigh() {
		for(int i=0; i<rating.length; i++)
			if(rating[i][0] != 0) rating[i][1] = cash / rating[i][0]; 
		
		int value = rating[0][1];
		int ind = 0;
		for(int i=1; i<rating.length; i++) {
			if(value > rating[i][1]) {
				value = rating[i][1];
				ind = i;
			}
		}
		return ind;
	}
	//Find coins with the smallest weight
	private int search() {	
		int div = 0;
		for(int p = weigh() ; p<rating.length; p++) {						
			
			if(rating[p][1] != 0 && rating[p][0] != 0   && div < rating[p][1]) {
				if(div <= cash) {
					div = rating[p][0];
					System.out.println("Value = " + div + " Rating - " + rating[p][1]);
					return p; 
				}
			}
		}
		return EXIT;
	}
	//Сalculation of results
	public void calculate() {
		
		if(cash != 0) {
			for(int p = 0, resoult = 0; cash > 0 ; ) {
				resoult = search();
				if(resoult != EXIT) {
					
					if(cash - rating[resoult][0] >= 0 && cash - rating[resoult][0] >= rating[rating.length - 1][0] ) {//|| resoult == rating.length - 1 && cash - rating[resoult][0] >= 0) {
						
						p = resoult;
						cash -= rating[resoult][0];
						unit[resoult][1] ++;
						continue;	
					}
					else if(cash - rating[resoult][0] * rating[resoult][1] == 0) {
						
						cash -= rating[resoult][0] * rating[resoult][1];
						unit[resoult][1] ++;
						break;
					}
					else {
						
						cash += rating[p][0];
						rating[p][0] = 0;
						unit[p][1] --;
						continue;
					}
				}
				else {
					
					System.out.println("calculation is impossible...");
					return;
				}
			}
			output();
		}
	}
	//Print results
	private void output() {
		System.out.println("issued coins:");
		for(int i = 0; i < rating.length; i++){
			System.out.println(unit[i][0] + " - " + unit[i][1]);
		}
	}
	
    public static void main( String[] args )
    {
    	Scanner con = new Scanner(System.in) ;
		int code = 0, cash = 0;    
		try {
			
			do {
					System.out.print("\n\nmoney: ");			
					cash = 	con.nextInt();			
					App aut = new App(cash);
					aut.calculate();
					System.out.println(" next/exit - n/e ?");
					
				}
				while ( 101 != (code = System.in.read())) ; 
		} 
		catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
    }
}
